import javafx.util.Pair;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author hewei
 * @version 1.0
 * @description: 923. 三数之和的多种可能
 * @date 2022/9/20 16:14
 */

public class ThreeSumMulti {

    public static void main(String[] args) {
        int[] nums = {1,1,2,2,3,3,4,4,5,5};
        System.out.println(new ThreeSumMulti().threeSumMulti(nums, 8));
    }

    public int threeSumMulti1(int[] arr, int target) {
        Arrays.sort(arr);
        HashMap<Integer, Pair<Integer, Integer>> map = new HashMap<>();
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int temp = arr[i];
            if (!map.containsKey(temp)) {
                map.put(temp, new Pair<>(i, 1));
            } else {
                Pair<Integer, Integer> pair = map.get(temp);
                map.put(temp, new Pair<>(pair.getKey(), pair.getValue() + 1));
            }
        }
        long ans = 0;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                int temp = target - arr[i] - arr[j];
                int binarySearch = binarySearch(arr, temp, j + 1, n - 1);
                if (binarySearch != -1) {
                    Pair<Integer, Integer> pair = map.get(temp);
                    ans += pair.getValue() - (binarySearch - pair.getKey());
                }
            }
        }
        return (int) (ans % (1e9 + 7));
    }

    public int binarySearch(int[] arr, int target, int l, int r) {
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (arr[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return arr[l] == target ? l : -1;
    }

    public int threeSumMulti(int[] arr, int target) {
        Arrays.sort(arr);
        int mod = (int) (1e9 + 7);
        int ans = 0;
        int n = arr.length;
        for (int i = 0; i < n - 2; i++) {
            int temp = target - arr[i];
            int l = i + 1;
            int r = n - 1;
            while (l < r) {
                if (arr[l] + arr[r] < temp) {
                    ++l;
                } else if (arr[l] + arr[r] > temp) {
                    --r;
                } else if (arr[l] == arr[r]) {
                    ans += (r - l + 1) * (r - l) / 2;
                    ans %= mod;
                    break;
                } else {
                    int count1 = 1;
                    int count2 = 1;
                    while (l + 1 < r && arr[l + 1] == arr[l]) {
                        ++l;
                        ++count1;
                    }
                    while (r - 1 > l && arr[r - 1] == arr[r]) {
                        --r;
                        ++count2;
                    }
                    ++l;
                    --r;
                    ans += count1 * count2;
                    ans %= mod;
                }
            }
        }
        return ans;
    }
}